package 左哥算法.ch06二叉树;

import java.util.Comparator;
import java.util.LinkedList;
import java.util.Objects;
import java.util.Queue;

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;

    public TreeNode() {
    }

    public TreeNode(Integer val) {
        this.val = val;
    }

    public TreeNode(Integer val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }

    //创建一棵深度为k的满二叉树
    public static int start = 1;

    public void newTree(int k) {
        if (k == 1) {
            this.val = start;
            return;
        }
        start = this.val;
        this.left = new TreeNode();
        this.right = new TreeNode();
        start++;
        this.left.val = start;
        this.left.newTree(k - 1);
        start++;
        this.right.val = start;
        this.right.newTree(k - 1);
    }

    /**
     * 将一个层序遍历的数组转换为二叉树
     * 队列思路：
     * 1.预先将数组第一位初始化为头节点，并预先对其入队
     * 2.准备三个变量，分别是当前节点的索引、和左右节点的索引
     * 4.将节点出队，（判断是否为空）对该节点左右节点分别赋值，若左右节点不存在则赋null，将左右节点入队，对当前索引++
     * 5.重复4直到数组遍历完成
     *
     * @return
     */
    public static TreeNode newLevelTree(Integer[] arr) {
        if (arr.length == 0 || arr[0] == null) {
            return null;
        }
        TreeNode root = new TreeNode(arr[0]);
        Queue<TreeNode> queue = new LinkedList<>();
        int left = -1, right = -1;
        queue.add(root);
        for (int index = 0; index < arr.length; index++) {
            TreeNode node = queue.poll();
            if (node != null) {
                left = index * 2 + 1;
                right = index * 2 + 2;
                node.left = left < arr.length && arr[left] != null ?     //左侧存在且不为空
                        new TreeNode(arr[left]) : null;
                node.right = right < arr.length && arr[right] != null ?     //左侧存在且不为空
                        new TreeNode(arr[right]) : null;
                queue.add(node.left);
                queue.add(node.right);
            }
        }
        return root;
    }

    public String toString() {
        return val + " ";
    }
}
